package offerbook;

import baseclass.d_list.Code07_IsAnnulateList_有环链表;
import baseclass.d_list.Code08_判断两个单向无环链表是否相交;
import utils.ListNode;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * 链表公共部分，链表第一个交点。链表是否有环等问题，见
 * {@link Code07_IsAnnulateList_有环链表}
 * {@link Code08_判断两个单向无环链表是否相交}
 * @date 2020/3/10 18:05
 */
public class Code37_CommonPart_链表公共部分 {
    //方式1：两次遍历。时间O(n²),空间O(1)
    public static ListNode process1(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        ListNode p2;
        while (p1 != null) {
            p2 = headB;
            while (p2 != null) {
                if (p2 == p1) return p1;
                p2 = p2.next;
            }
            p1 = p1.next;
        }
        return null;
    }

    //方式2：用set。时空都是O(n)
    public static ListNode process2(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        ListNode p1 = headA;
        while (p1 != null) {
            set.add(p1);
            p1 = p1.next;
        }
        p1 = headB;
        while (p1 != null) {
            if (set.contains(p1)) return p1;
            p1 = p1.next;
        }
        return null;
    }

    //方式3：用两个stack。遍历链表装入stack，然后pop，找出第一个pop不等的数据。时空都是O(n)
    public static ListNode process3(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();
        while (p1 != null) {
            stack1.push(p1);
            p1 = p1.next;
        }
        p1 = headB;
        while (p1 != null) {
            stack2.push(p1);
            p1 = p1.next;
        }

        //p1记录上一次pop的数据。
        p1 = null;
        //当stack1与stack2栈顶不同，就返回p1.否则出栈，把p1重新赋值
        while (!stack1.isEmpty() && !stack2.isEmpty() && stack1.peek() == stack2.peek()) {
            p1 = stack1.pop();
            stack2.pop();
        }
        return p1;
    }

    //方式4:统计两个链表的长度len1,len2。让长的先走差值，然后一起走。如果有相交，必定会一起走到相同点
    public static ListNode process4(ListNode headA, ListNode headB) {
        int len1 = getLength(headA);
        int len2 = getLength(headB);
        //让p1指向长的链表，p2指向短的
        ListNode p1 = len1 >= len2 ? headA : headB;
        ListNode p2 = len1 >= len2 ? headB : headA;
        int step = Math.abs(len1 - len2);
        while (step-- != 0) p1 = p1.next;
        //让p1与p2一起走
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        //p1和p2可能都是空
        return p1;
    }

    private static int getLength(ListNode head) {
        ListNode cur = head;
        int len = 0;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        return len;
    }

    /**
     * 方法5：通过测试，是一个结论
     * 看下面的链表例子：
     * 0-1-2-3-4-5-null
     * a-b-4-5-null
     * 代码的if-else语句，对于某个指针p1来说，其实就是让它跑了连接好的的链表，长度就变成一样了。
     * 如果有公共结点，那么指针一起走到末尾的部分，也就一定会重叠。看看下面指针的路径吧。
     * p1： 0-1-2-3-4-5-null(此时遇到if-else)-a-b-4-5-null
     * p2: a-b-4-5-null(此时遇到if-else)0-1-2-3-4-5-null
     * 因此，两个指针所要遍历的链表就长度一样了！
     * 如果两个链表存在公共结点，那么p1就是该结点，如果不存在那么p1将会是null。
     */
    public static ListNode getIntersectNode5(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        ListNode p1 = head1;
        ListNode p2 = head2;
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
            // p1 == p2 为公共的点  或者都为null
            if (p1 != p2) {
                if (p1 == null) p1 = head2;
                if (p2 == null) p2 = head1;
            }
        }
        return p1;
    }

}
